package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author shiminghui
 * @date 2025/3/15 17:31
 * @description: TODO
 */
public class _050_贪心算法 {
    int min = Integer.MAX_VALUE;


    @Test
    public void test() {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(change(amount, coins));
        System.out.println(min);
    }


    /**
     * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
     * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
     * 假设每一种面额的硬币有无限个。
     * 题目数据保证结果符合 32 位带符号整数。
     */
    public int change(int amount, int[] coins) {
        Arrays.sort(coins);
        HashMap<entry, Integer> map = new HashMap<>();
        return change(amount, coins, coins.length - 1, map, new AtomicInteger(0));
    }

    private int change(int amount, int[] coins, int index, HashMap<entry, Integer> map, AtomicInteger coinCount) {
        if (amount == 0) {
            min = Math.min(coinCount.get(), min);
            return 1;
        }
        if (index == -1) {
            return 0;
        }
        int count = 0;
        if (!map.containsKey(new entry(amount, coins[index]))) {
            int num = amount / coins[index];
            for (int i = num; i >= 0; i--) {
                coinCount.getAndAdd(i);
                count += change(amount - i * coins[index], coins, index - 1, map, coinCount);
                coinCount.getAndAdd(-i);
            }
            map.put(new entry(amount, coins[index]), count);
        } else {
            count = map.get(new entry(amount, coins[index]));
        }

        return count;
    }

    private class entry {
        private int amount;
        private int coin;

        public entry(int amount, int coin) {
            this.amount = amount;
            this.coin = coin;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            entry entry = (entry) o;
            return amount == entry.amount && coin == entry.coin;
        }

        @Override
        public int hashCode() {
            return Objects.hash(amount, coin);
        }
    }

}
